#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    bool hasGroupsSizeX(vector<int> &deck)
    {
        int N = deck.length;
        int[] count = new int[10000];
        for (int c : deck)
            count[c]++;

        vector<int> values;
        for (int i = 0; i < 10000; ++i)
        {
            if (count[i] > 0)
            {
                values.emplace_back(count[i]);
            }
        }

        for (int X = 2; X <= N; ++X)
        {
            if (N % X == 0)
            {
                bool flag = 1;
                for (int v : values)
                {
                    if (v % X != 0)
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag)
                {
                    return true;
                }
            }
        }
        return false;
    }

    //欧几里得算法：求最大公约数
    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

    bool hasGroupsSizeX(vector<int>& deck) 
    {
        //记录每种牌的数量，假设为a1, a2, a3, a4, ... , ak;
        //对于a1~ak,都能被x >= 2整除, =>x是a1~ak的一个公约数
        //那么可以求a1~ak的最大公约数，判断一下公约数是否大于>=2，如果是，这表明存在这个x

        unordered_map<int, int> cnt;
        for(auto x : deck) cnt[x]++;

        int d = 0;
        //这个for循环就很巧妙
        //采用了结构化绑定（C++17新特性）巧妙地遍历了哈希表中的元素
        //d = 0,这样可以计算从a1到ak的最大约数
        //一旦for循环中出现了最大公约数小与2的情况，那么后面求最大公约数的过程中，也不会在出现>=2的情况，能顺利返回false 
        for(auto [k,v] : cnt) d = gcd(d, v);
        return d >= 2;
    }
};
int main()
{
    Solution s;
    vector<int> deck = {1, 2, 3, 4, 4, 3, 2, 1};
    cout << s.hasGroupsSizeX(deck) << endl;
    return 0;
}